package 第七周;

/*
 * @author  YxinMiracle
 * @date  2022-05-06 19:49
 * @Gitee: https://gitee.com/yxinmiracle
 */

import java.util.Arrays;

public class 打家劫舍 {

    public int rob(int[] nums) {
        int n = nums.length;
        int[] newNum = new int[n+1];
        for (int i = 1; i <= n; i++) {
            newNum[i] = nums[i-1];
        }

        int[][] f = new int[n+1][2];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(f,-100000000);
        }
        f[0][0] = 0;

        // 1-n
        for (int i = 1; i <= n; i++) {
            // 不偷
            f[i][0] = Math.max(f[i][0],Math.max(f[i-1][0],f[i-1][1]));
            // 偷
            f[i][1] = Math.max(f[i][1],f[i-1][0]+newNum[i]);
        }

        return Math.max(f[n][0],f[n][1]);
    }

}
